home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / Hack / MISC / PSEUDO~1.ZIP / PSEUDO~1.TXT
Encoding:
Text File  |  1996-04-27  |  39.3 KB  |  848 lines

  1.  
  2.  
  3. Pseudo-Network  Drivers and  Virtual  Networks
  4.  
  5. S.M.  Bellovin* smb@ulysses.att.com
  6.  
  7. AT&T  Bell  Laboratories Murray  Hill,  New  Jersey  07974
  8.  
  9. ABSTRACT
  10.  
  11. Many  operating  systems  have  long  had pseudo-teletypes,  inter-process
  12. communication channels that provide terminal semantics on one end, and a
  13. smart server program on the other.  We describe an analogous concept,
  14. pseudo-network drivers.  One end of the driver appears to be a real network
  15. device, with the appropriate interface and semantics; data written to it
  16. goes to a program, however, rather than to a physical medium.  Using this
  17. and some auxiliary mechanisms, we present a variety of applications,
  18. including system test, network monitoring, dial-up TCP/IP, and ways to both
  19. improve and subvert network security.  Most notably, we show how
  20. pseudo-network devices can be used to create virtual networks and to provide
  21. encrypted communications capability.  We describe two implementations, one
  22. using a conventional driver for socket-based systems, and one using stream
  23. pipes for System V.
  24.  
  25. 1.  INTRODUCTION
  26.  
  27. Many operating  systems have long had pseudo-teletypes, inter-process
  28. communication channels that provide terminal semantics on one end, and a
  29. smart server program on the other.  In the same vein, we have implemented a
  30. pseudo-network driver.  To the kernel, and in particular to IP, it appears
  31. to be a device; instead of transmitting the bits over a wire, the output
  32. packets are sent to a program.  Similarly, packets written by the program
  33. are delivered to the network input handlers, exactly as if they were
  34. received over a real device.  The general flow of control is shown in Figure
  35. 1.
  36.  
  37. IP (or another network protocol) hands packets to the bottom half of Pnet;
  38. the top half of the driver passes them to a server program, which can
  39. communicate with other servers.  Similarly, the server can generate packets
  40. and pass them to the driver; these are in turn sent to IP.
  41.  
  42. There are two  general  implementation  techniques available.  For
  43. socket-based systems, such as SunOS and 4.3bsd, we have implemented a
  44. standard network device driver; a detailed description of the driver is
  45. given below.  For stream [Ritc84] implementations of TCP/IP, a simple stream
  46. pipe may suffice, possibly with no kernel changes whatsoever; again, details
  47. are given below.
  48.  
  49. ________________
  50.  
  51. *  Author's  address:  Steven  M.  Bellovin,  Room  3C-536B,  AT&T  Bell
  52. Laboratories, 600 Mountain Avenue, Murray Hill, New Jersey 07974.
  53.  
  54. Server
  55.  
  56. Pnet (driver)
  57.  
  58. Pnet (network)
  59.  
  60. IP
  61.  
  62. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . User Kernel
  63.  
  64. other servers
  65.  
  66. Figure 1. The Pseudo-Network Driver
  67.  
  68. Although  the  primary  focus  of  the  driver  is  TCP/IP, [Fein85,
  69. Come88] the socket version is actually quite general; it can handle any
  70. address families supported by the rest of the kernel.  It has been tested on
  71. SunOS 4.0.1 and 4.0.3; with minor changes, it should run on 4.2bsd, 4.3bsd,
  72. and other related operating systems.
  73.  
  74. 2.  RE-INJECTION TECHNIQUES AND ISOLATED INTERFACES
  75.  
  76. A  number  of  uses  for Pnet involve re-injecting a  transformed  packet
  77. into the kernel for further processing.  For example, the packet could be
  78. encrypted, repackaged with a new IP header and a protocol number indicating
  79. encryption, and sent on its way.  Before discussing Pnet proper, it is worth
  80. examining possible mechanisms for re-injection; it is not trivial to
  81. implement, but is quite necessary.
  82.  
  83. The  first,  and  most  obvious  way,  is  to  build  a  new  packet,  and
  84. simply write() it to the Pnet device, under the assumption that IP will then
  85. forward it to the proper destination. However, many IP modules will not
  86. forward packets, either for security reasons or because forwarding packets
  87. is the business of gateways, not hosts. [Brad89]
  88.  
  89. For socket-based implementations, a second approach is to create a raw IP
  90. socket, and use it to re-inject the packets.  Unfortunately, while that
  91. mechanism is suitable for transmitting the encrypted packets, it fails on
  92. decryption.  Decrypted packets -- received by a user-level process bound to
  93. that IP protocol number -- should carry the IP source address of the
  94. original sender; the raw IP socket interface insists that packets carry
  95. authentic local source addresses. While it may be possible to kludge around
  96. this requirement, a cleaner solution can be obtained by implementing a new
  97. raw protocol in the Internet address family; this protocol would permit
  98. specification of an arbitrary IP header. 1
  99.  
  100. We  have  opted  to  implement  a  variant  of  this  mechanism.  Rather
  101. than create a separate interface solely for packet re-injection, we have
  102. overloaded the address family field used by pnetwrite.  As noted, these
  103. packets are passed directly to the IP output routine, rather than the input
  104. routine.  This interface must be used with great care.  Only minimal checks
  105. are done, to guard against kernel panics.  No attempt is made to provide
  106. standard packet input processing, such as checksum validation, time-to-live
  107. counter decrementing, or option processing.  More seriously, the packet is
  108. not checked to see if it is destined for this host.  If it is, when the real
  109. driver receives the packet, it must pass it to IP's input routine.  Of
  110. course, if the packet was destined for Pnet's local address, it will be
  111. delivered again to the server, possibly causing a loop. Pnet broadcast
  112. packets are a particularly nasty case of this.
  113.  
  114. Implementing  re-injection  is  harder  for  stream  implementations.  The
  115. only path into IP is the transport protocols' interface; for these, IP
  116. expects to fill in the source address, etc.  Some sort of raw channel is
  117. needed; this might require changes to IP.
  118.  
  119. An  alternative  to  packet  re-injection  is  to  implement interface
  120. isolation.  If an interface is marked as isolated (presumably via ifconfig),
  121. packets from it are not forwarded.  Thus, packets arriving via the Pnet
  122. driver could be forwarded, while packets arriving on an external link would
  123. not.  Obviously, source routing would be disabled for isolated interfaces
  124. also.  A final aspect of interface isolation, possibly controlled by a
  125. different bit, is to accept packets arriving on an isolated interface if and
  126. only if they are destined for the machine's IP address on that interface. 
  127. That is, we do not permit the implicit forwarding to an alternate address
  128. associated with another network interface on the gateway. 2
  129.  
  130. For  some  purposes,  a  simple  isolation  bit  is  insufficient;  one
  131. would need isolation groups that define allowable forwarding patterns. 
  132. Finally, one could escalate to full address screening, [Mogu89] though if
  133. encryption is univerally performed that is probably not necessary.
  134.  
  135. 3.  APPLICATIONS
  136.  
  137. The Pnet driver has many uses, ranging from the trivial to the complex.  A
  138. few are discussed below.  We have implemented some of these, and plan to
  139. implement others.
  140.  
  141. 3.1  System Test
  142.  
  143. It is often difficult to test protocol implementations.  The usual approach
  144. is to use sophisticated network monitors to observe the traffic and to
  145. create test packets.  Such techniques, though, are expensive and often
  146. uncertain -- fast hosts can easily overrun some network monitors. Pnet,
  147. though, makes life much easier -- a host program can catch or generate all
  148. test packets.
  149.  
  150. Care  must  be  taken  when  emulating  a  protocol  in  a  program;  some
  151. features are more difficult to emulate than others.  During development of
  152. Pnet, we ran into trouble with fragmented ICMP ECHO packets; generating
  153. proper replies required receipt and reassembly of all
  154.  
  155. ________________
  156.  
  157. 1.  Some people may object that allowing a host process to impersonate an IP
  158. address is a security risk.  First, this facility is only available to root;
  159. a rogue super-user has easier ways to spoof IP addresses.  Second, the very
  160. existence of Pnet allows injection of packets with arbitrary addresses. 
  161. Finally, as shown elsewhere, [Bell89] using an IP address for authorization
  162. is very unsafe in any event.
  163.  
  164. 2.  This  does  not  necessarily  provide  enough  security  for  the
  165. gateway machine.  ICMP packets can have a global effect, regardless of the
  166. destination address used.
  167.  
  168. fragments.
  169.  
  170. 3.2  Netspy
  171.  
  172. The Pnet driver can be used to monitor conversations.  A routing entry can
  173. be constructed to direct traffic for a particular destination to the Pnet
  174. driver.  After examination, the packet can be re-injected, adding IP Loose
  175. Source routing to carry the packet to the next hop.
  176.  
  177. The potential for abuse of this capability is, of course, obvious.
  178.  
  179. 3.3  Non-IP Relays
  180.  
  181. In  some  environments,  it  is  necessary  to  send  IP  packets  over
  182. media for which IP drivers do not exist.  Pnet provides a simple mechanism
  183. for accomplishing this; a program can retrieve the IP packets via the Pnet
  184. driver, encapsulate them for some other protocol, and transmit them to the
  185. far end.
  186.  
  187. This  can  be  also  be  done  in  some  situations  where  one  side
  188. implements an IP driver directly. For example, some implementations of
  189. Datakit (R) VCS support contain an IP interface, while others do not.  The
  190. latter can use Pnet to transmit packets to and from IP; at the far end of
  191. the Datakit VCS circuit, IP can handle them directly.
  192.  
  193. 3.4  Replacing SLIP
  194.  
  195. The  conventional  mechanism  for  sending  IP  packets  over  tty  lines
  196. -- SLIP, or Serial Line IP [Romk88] -- requires oddball code in the kernel. 
  197. A line discipline is used for framing, which is reasonable enough; however,
  198. some implementations require a dummy process to linger to keep the line
  199. open, or some mechanism to prevent the normal close operations from taking
  200. place.  Furthermore, dial-up SLIP operation is awkward, though it has been
  201. done. [Lanz89] All of that can be bypassed using Pnet.  A single process can
  202. handle packets for all of the SLIP destinations; it can make calls as
  203. needed, transmit and receive data, etc.  To be sure, a line discipline may
  204. be needed in any event, to buffer the incoming characters and avoid the need
  205. to wake up the SLIP daemon each time, but much of the complexity could be
  206. eliminated.
  207.  
  208. A Pnet implementation  has  the  side-effect  that  all  of  the  SLIP
  209. destinations would share the same IP network number.  This is probably a
  210. good idea -- using an entire network for each point-to-point link is
  211. wasteful, though presumably one could subnet a class C network and use it
  212. for 64 SLIP links 3 -- but it requires good routing protocols to handle the
  213. point-to-point connections.  The IP model normally requires that an
  214. interface driver be able to reach every connected host directly; this is
  215. often not the case with SLIP.
  216.  
  217. 3.5  Bypassing Security Controls
  218.  
  219. The Pnet driver can also  be  used  to  implement a  bypass for some common
  220. security controls. Assume, for example, a paranoid gateway that was
  221. configured to allow only electronic mail traffic; this would be configured
  222. to accept TCP packets with a source or destination port of 25, and to reject
  223. all others. [Mogu89] Two co-operating parties could set up a TCP circuit
  224. between Pnet servers, and simply assign one end to port 25.  Assuming
  225. suitable routing information were exchanged, each end would have access to
  226. the other's IP networks.
  227.  
  228. ________________
  229.  
  230. 3.  At least 2 bits must be used for every subnet, as the host addresses 0
  231. and -1 are still reserved.
  232.  
  233. Obviously, in this sort of situation two parties who merely wished to leak
  234. information could do so rather more simply.  The point is that Pnet allows
  235. IP-level access, and is thus far more damaging.
  236.  
  237. 3.6  More Reliable Datagrams
  238.  
  239. In  the  current  congested  Internet  environment,  datagram  services  are
  240. hard to use.  Too many packets are dropped or delayed, leading to excessive
  241. retries and/or congestion. [Nowi89] If a TCP-based relay process is used
  242. with Pnet, application-level retry timers can be turned off, and advantage
  243. can be taken of recent TCP performance improvements. [Karn87, Jaco88]
  244. Similarly, if the underlying network is prone to data corruption, this
  245. mechanism is useful when using systems that turn off UDP checksumming.
  246.  
  247. If  this  strategy  is  adopted,  great  care  must  be  taken  if
  248. application-level retry timers are still used.  TCP segments can be delayed
  249. or lost as easily as UDP packets; however, since TCP will retransmit on its
  250. own, it is highly undesirable for the application to do so as well.
  251. Application-level retransmissions will simply generate extra load; they will
  252. not provide better service.
  253.  
  254. 4.  VIRTUAL NETWORKS
  255.  
  256. There  are  a  number  of  protocols,  typically  broadcast-based  ones,
  257. that operate properly only within a single IP network.  If the machines that
  258. wish to run such a protocol are geographically dispersed, it may not be
  259. feasible to connect them to the same net.  Using Pnet, though, this can be
  260. accomplished reasonably easily: a server could declare the interface to be a
  261. broadcast network, and transmit broadcast packets to all appropriate
  262. destinations.  This is an example of a virtual network.  While there is an
  263. obvious efficiency loss in broadcast virtual networks, the gain in
  264. functionality may make it worthwhile for some applications.
  265.  
  266. Virtual  networks  have  other  uses  as  well.  For  example,  consider
  267. the case of a large corporation with many internal TCP/IP networks, and a
  268. single gateway to the Internet.  It may be desirable to allow a very few
  269. selected hosts access to the Internet through the gateway; most, though,
  270. would be blocked for security reasons.  The selected hosts and the gateway
  271. could form a virtual network; only its address would be advertised to the
  272. outside world.
  273.  
  274. A  more  general  way  to  phrase  this  is  that  virtual  networks  allow
  275. for routing and control independent of the physical topology.  This can be
  276. used to implement many different useful schemes, including ``roamer hosts''.
  277.  
  278. Virtual  network  packets  may  be  carried  by  TCP,  UDP,  or  IP.  If
  279. UDP is used, checksumming should be turned off for that connection; it
  280. represents needless expense, as the encapsulated packet will undergo further
  281. validity checking when delivered to its ultimate destination.
  282.  
  283. 4.1  An Encrypted Virtual Network
  284.  
  285. Perhaps  the  most  interesting  use  of Pnet is  to  implement  encryption,
  286. access control, and authentication mechanisms.  We shall spend some time on
  287. a detailed description of just such a system; it is currently under
  288. development.  Since ours is loosely modeled on the Blacker Front End [BFE,
  289. Mund87] but is much less secure, we dub it Greyer.  There are two principal
  290. uses for Greyer: providing end-to-end encryption between a pair of hosts
  291. communicating over an insecure network, and providing network-level
  292. encryption between a pair of gateways, each of which is protecting a group
  293. of naive hosts.  We will consider each design in turn.
  294.  
  295. At  first  blush,  providing  end-to-end  encryption  is  simple.  Create  a
  296. virtual network, as described above.  When a host wishes to make a secure
  297. call to a destination, it uses the destination network's address on the
  298. virtual network.  All of the packets are thus delivered to the Pnet server,
  299. which encrypts them and sends them along.  These servers have addresses on
  300. the insecure physical network.  The destination server receives the packet,
  301. decrypts it, and writes it on the Pnet device; in the kernel, the packet is
  302. recognized as destined for the local host, and is delivered to the
  303. application in the usual fashion.
  304.  
  305. There  is  a  catch,  however.  One  of  the  benefits  of  encryption  is
  306. the implied authentication it provides.  Applications which believe they are
  307. conversing over the secure virtual net may quite reasonably extend much
  308. greater trust.  Unfortunately, packets with a virtual net destination
  309. address may be delivered to a host over its physical network interface;
  310. these packets have not been validated in any way.  They will nevertheless be
  311. accepted.
  312.  
  313. The  easiest  solution  is  the  interface  isolation  mechanism  described
  314. earlier.  Note that we must isolate the physical network, not the virtual
  315. one.  That is, we will accept packets over the virtual interface for either
  316. address; we do not wish to accept packets for the presumed-secure virtual
  317. address over the physical link.  If the host has more than one physical
  318. address, this solution is too simplistic; it may be necessary to use
  319. isolation groups.
  320.  
  321. Some  may  object  that  this  is  not  a  real  problem.  After  all,  even
  322. though forged packets to the protected address may be sent via the physical
  323. network, replies will be sent via the virtual network, and hence will be
  324. encrypted.  Unfortunately, there are ways to attack hosts that rely on IP
  325. addresses for authentication, even if responses are not heard. [Bell89,
  326. Morr85] More simply, IP source routing could be used, thereby forcing the
  327. target host to reply via the same insecure path.
  328.  
  329. Gateways and Greyer Gateways  using Greyer may  require  interface
  330. isolation as well.  For inbound traffic, the rationale is simple: we do not
  331. wish unauthorized packets to enter the protected subnet.  If the interface
  332. were not isolated, an enemy could simply use the physical network address of
  333. a target host.
  334.  
  335. Outbound  traffic  may  need  to  be  restricted  also.  In  a  classified
  336. environment, for example, individual users may not select the data
  337. transmission mode; that is up to the administrator.  It is thus necessary to
  338. guard against internal traffic being routed directly to the external
  339. interface. On the other hand, we cannot simply turn off packet-forwarding,
  340. or we would have no way to deliver outbound packets to the Pnet server.
  341.  
  342. Our  model,  then  is  this:  hosts  behind  the Greyer gateway  forward
  343. their packets to it to reach a remote secure host.  On the gateway, routing
  344. table entries specify that the next hop is on the virtual net; this forces
  345. the packets to be delivered to the Pnet server for encryption. The packets
  346. are encrypted and encapsulated, and transmitted over the insecure network to
  347. a remote server.  It must then decrypt them and hand them back to IP.  We
  348. may use re-injection; if the host will permit packet-forwarding from the
  349. Pnet interface, a write() over the Pnet device will serve.
  350.  
  351. As  noted,  encryption  provides  implied  authentication.  It  also
  352. provides authorization: the key distribution center may, at its option,
  353. decline to issue a key for a conversation deemed administratively
  354. prohibited.  In fact, the Greyer mechanisms could simply be used for
  355. authorization without bothering with transmitting the encrypted text at all,
  356. as in the Visa protocols. [Estr89] There are obvious risks of address
  357. forgery here, of course.
  358.  
  359. Encapsulation for Greyer There  are  two  issues  to  consider  when
  360. deciding how to encapsulate Greyer packets for transmission over the
  361. insecure network: how should session key information be distributed, and
  362. what transport mechanism should be used?  The two questions are related.
  363.  
  364. First,  we  assume  that  the Greyer server  will  not  have  keys  for
  365. each possible destination; rather, it will use something like
  366. Needham-Schroeder [Need78, Denn81, Need87] or Kerberos [Stei88]
  367.  
  368. to  obtain  a  session  key.  It  is  therefore  necessary  to  transmit
  369. this session key to the remote Greyer server.  If TCP is used as the
  370. transport mechanism, the solution is obvious: send the session key at the
  371. start of each connection.  If a key expires, the connection may be torn down
  372. and a new one constructed.
  373.  
  374. If,  on  the  other  hand,  a  datagram  mechanism  is  used  (either  UDP
  375. or a new IP protocol type), the problem is a bit harder.  One possibility is
  376. to send a special packet containing the key to the remote Greyer server;
  377. depending on the reliability of the underlying network, it may be desirable
  378. to await an acknowledgement before transmitting any packets that use the
  379. key.  More likely, we will use the SP3 protocol from SDNS. [SP3]
  380.  
  381. A  final  possibility  is  to  include  the  encrypted  key  in  each
  382. packet.  This preserves the stateless nature of IP gateways, at the obvious
  383. cost in bandwidth.  The exact choice depends heavily on the characteristics
  384. of the physical network; we will address this question further when Greyer
  385. is implemented.
  386.  
  387. 5.  SOCKET IMPLEMENTATION DETAILS AND ALTERNATIVES
  388.  
  389. The  socket Pnet driver  consists  of  two  distinct  halves,  a  network
  390. driver and a character device driver.  Each contains the usual entry points:
  391. attach, output, and ioctl for the network driver, and open, close, read,
  392. write, ioctl, and select for the character driver.  We describe each half in
  393. turn.
  394.  
  395. The  network  output  routine  (pnoutput)  is  quite  straight-forward.  If
  396. the character half of the driver is not open, packets are rejected with code
  397. ENETDOWN.  Otherwise, the packet is queued for the server program.  A header
  398. containing the destination address is prepended to the packet, in the form
  399. of a single struct sockaddr.  It is important that the server program use
  400. this address to determine the header, rather than looking at the packet
  401. header; to do otherwise would require that it duplicate most of the
  402. functions of IP.  If the program's input queue is full, the packet is
  403. discarded and ENOBUFS is returned to the caller.  No attempt is made to loop
  404. back packets destined for a local address; that is left to the server.
  405.  
  406. The  rest  of  the  network  driver  half  is  comparatively  trivial.  One,
  407. perhaps incorrect, decision: if the interface is turned off via
  408. SIOCSIFFLAGS, the server program is sent an EOF message.
  409.  
  410. The  character  driver  is  a  bit  more  complex. Pnetread blocks  until
  411. data has been enqueued by pnoutput; if FASYNC mode has been selected, it
  412. returns an error code instead if the queue is empty.
  413.  
  414. Pnetwrite is more problematic for several reasons.  First, it cannot accept
  415. just a raw packet; it needs address family information in order to route the
  416. packet to the proper protocol.  While a simple short would suffice, the
  417. current driver requires a full struct sockaddr; this simplifies use of the
  418. same data structures for the input and output halves of the program.  The
  419. other fields in this structure are currently unused, though that may change
  420. in the future.
  421.  
  422. A  second  complication  is  the  need  to re-inject packets  into  the
  423. system, as described above.  If the high-order bit of the address family is
  424. on, the packet is passed to the output routine of that protocol, rather than
  425. the input routine.  Currently, only AF_INET is supported for this option.
  426.  
  427. Finally, it is not obvious how to block if the protocol input queue is full. 
  428. It is easy enough for the server process to sleep; however, there is no
  429. ``interrupt routine'' to awaken it when the queue drains.  Accordingly, a
  430. timer routine is used to poll the queue status.
  431.  
  432. Pnetselect has a similar problem; additionally, since it lacks information
  433. on which protocol input queue is desired, it cannot assert definitively that
  434. space is available.  As a heuristic, it queries the status of the last queue
  435. to which a write() was attempted.
  436.  
  437. Pnetioctl permits  the  server  to  set  the IFF_BROADCAST and
  438. IFF_POINTOPOINT flags for the interface; since the driver has no way of
  439. knowing the intended use of the interface, it cannot make a default choice. 
  440. Additionally, the server can set and reset IFF_UP; while this flag can be
  441. set via SIOCSIFFLAGS, use of that ioctl() is restricted to root.
  442.  
  443. It  is  also  possible  for  the  server  to  change  the  maximum
  444. transmission unit (MTU) allowed for the interface.  If another network
  445. medium is used to relay Pnet packets, the MTU for the Pnet interface should
  446. be set to the MTU of the medium minus any required headers, to avoid
  447. fragmentation.
  448.  
  449. Rejected Alternatives An alternative implementation technique would have
  450. been to replace the character driver with a new socket address family.  That
  451. would have allowed use of sendto() and recvfrom() system calls to pass the
  452. auxiliary address, rather than requiring a prepended header.  Similarly,
  453. much of the existing code for socket input/output could be used, rather than
  454. writing new routines.  This approach turned out to be infeasible for several
  455. reasons.
  456.  
  457. The first is simply a question of packaging.  As some systems are
  458. distributed, it is much easier to add new device drivers than to add new
  459. address families.  There is no accessible table to configure the domain
  460. structure for a new address family, nor are there vacant entries in the
  461. address family name space.  While some dormant entry could be reused, this
  462. seemed unwise. Nor is it possible to add additional entries to a binary
  463. system; there are several routines, and one table, that ``know'' how many
  464. address families there are. 4
  465.  
  466. A second reason is the permission  structure.  It  was useful to  permit
  467. non-root users to access this facility, at least during testing; this is
  468. very easily accomplished via the file system's permission mechanisms.  Doing
  469. the same for a socket family would have been awkward.
  470.  
  471. Finally,  the  device  driver  interface  is  much  more  standardized
  472. across releases than is the socket interface, and much more documentation
  473. exists for it.
  474.  
  475. It  should  be  noted  parenthetically  that  although  modifying
  476. distributed source code is not a priori a bad idea, it is often infeasible. 
  477. Source code distributions are sometimes not as current as binary-only
  478. distributions, and not everyone is licensed to receive source code.
  479.  
  480. ________________
  481.  
  482. 4.  Amusingly  enough,  the  SunOS  4.0  distribution  does  not  have
  483. AF_MAX set high enough for all of the address families named in socket.h.
  484.  
  485. 5.1  Performance of Socket-Based Pnet
  486.  
  487. Obviously,  performance  is  a  concern  when  packets  are  copied  to  and
  488. from user level an extra time before being transmitted.  To measure the
  489. performance of the socket implementation, we employed a modified version of
  490. ping(8).  This version transmitted a new ICMP ECHO packet immediately upon
  491. receipt of the response to the previous packet; it also printed the total
  492. elapsed time for the packet sequence.  Employing this technique, rather than
  493. measuring the per-packet round-trip time, allowed us to avoid problems with
  494. the coarse granularity of the system clock.  In the actual test, between a
  495. Sun 3/60 and a Sun 3/75, we measured performance at user-data lengths
  496. ranging from 0 to 1300 bytes.  Each measurement consisted of 100 ICMP
  497. packets; we repeated each test 100 times The goal was to acount for both the
  498. per-packet and per-byte overhead.  UDP was used as the transport mechanism,
  499. with checksumming turned off (the SunOS default).  Each test was repeated
  500. several times.  Note that the timing represents four copy operations on each
  501. byte: when sending the ECHO packet, when it is received on the target
  502. machine, when the response packet is sent, and when it is received.
  503.  
  504. Packet Size
  505.  
  506. per-packet time (ms.)
  507.  
  508. 0
  509.  
  510. .5
  511.  
  512. 1
  513.  
  514. 1.5
  515.  
  516. 2
  517.  
  518. 2.5
  519.  
  520. 3
  521.  
  522. 0 200 400 600 800 1000 1200 1400
  523.  
  524.  
  525. Pnet
  526.  
  527. Figure 2. Median ICMP ECHO Time
  528.  
  529. Figure 2  shows  the  median  times  in  milliseconds  for  each  packet
  530. size.  There is a glitch in the graph at around 500 bytes; this is most
  531. likely due to buffer allocation strategies.  Packets of more than 512 bytes
  532. -- counting the IP and ICMP headers, in this case -- are copied into a
  533. single mbuf cluster, rather than a chain of mbufs.
  534.  
  535. A  second  graph,  Figure 3,  shows  the  ratio  of  the  times.  It
  536. appeared that Pnet performed at one half to one third the speed of the raw
  537. underlying network.  To validate this, we used ftp(1) to copy a large file
  538. to /dev/null, after ensuring that the entire file was in the
  539.  
  540. -0
  541.  
  542. 1
  543.  
  544. 2
  545.  
  546. 3
  547.  
  548. Packet Size
  549.  
  550. time ratio
  551.  
  552. 0 200 400 600 800 1000 1200 1400
  553.  
  554. Figure 3. Ratio of Median Times
  555.  
  556. sender's buffer cache.  The  speed  ratio  was  noticeably  worse  than
  557. might be expected from the previous measurements, 3.4 to 1.  We attributed
  558. this difference primarily to CPU time consumption.  Copying the data to and
  559. from the Pnet driver is CPU-intensive; thus, Pnet is competing with ftp and
  560. TCP itself for processor time.  The ttcp throughput benchmark developed by
  561. Mike Muuss yielded similar results.  Visual observation of perfmeter during
  562. ttcp runs displays indicated that the receiving host sustained additional
  563. CPU load; the transmitting host actually had more idle time.
  564.  
  565. If  CPU  capacity  is  really  the  limiting  factor,  the  performance
  566. difference would not be seen if there was extra CPU capacity available. 
  567. Looked at another way, we can make available more CPU time per packet by
  568. slowing down the interarrival rate.  This was most easily accomplished by
  569. running similar tests across a long-haul link, in this case between Murray
  570. Hill, New Jersey, and Allentown, Pennsylvania.  IP access between the two
  571. sites is via a 1.344M bps point-to-point link; additionally, several other
  572. local area networks and gateways intervene at each end.
  573.  
  574. The  raw  throughput  graph  is  shown  in  Figure 4;  the  speed  ratio  is
  575. shown in Figure 5. Performance is a bit more variable, due to the vagaries
  576. of the shared link; as can be seen, though, the shapes of the two sets of
  577. graphs correspond nicely.  The Pnet link is only about 1.1 times slower than
  578. the direct link in this case.  A complication arose because of packet loss
  579. on the link; given the design of the test program, each dropped packet
  580. caused a one-second timeout before the next ICMP packet was sent.  We
  581. adjusted for this by subtracting one second from the total time for each
  582. such packet.
  583.  
  584. The  overhead of Pnet should  be  relatively  constant  for  a  given
  585. packet size, regardless of the link speed.  Figure 6 shows the difference in
  586. throughput for both sets of tests; as can be seen,
  587.  
  588. Packet Size
  589.  
  590. per-packet time (ms.)
  591.  
  592. 0
  593.  
  594. 5
  595.  
  596. 10
  597.  
  598. 15
  599.  
  600. 0 200 400 600 800 1000 1200 1400
  601.  
  602.  
  603. Figure 4. Median ICMP ECHO Time -- Long Haul
  604.  
  605. the two graphs are quite similar.
  606.  
  607. Finally,  the  same ftp and ttcp tests  were  run;  throughput  for Pnet was
  608. essentially the same as on the physical network.
  609.  
  610. 6.  A STREAM VERSION OF Pnet
  611.  
  612. On  a  system  with  a  good  stream  implementation  of  TCP/IP,  there  is
  613. no need for a Pnet driver.  The native drivers can be used instead, for all
  614. of the applications described above.  The mechanism is quite simple: create
  615. a stream pipe, and link one end of it to IP.  Issue the appropriate
  616. configuration ioctl() calls (i.e., to inform IP of the network number and IP
  617. address), and the stream will be treated the same as any other device
  618. driver.  For conventional devices, this configuration process is typically
  619. table-driven.  Since Pnet devices are dynamically created, a table is not
  620. usable; instead, the Pnet server must handle the process manually.
  621.  
  622. Shutting  down  a  pipe-based Pnet driver  is  often  difficult.  Shutdown
  623. may be disorderly; one or both ends of the pipe may be closed before IP's
  624. close routine is called.  It is therefore vital to detect M_HANGUP messages
  625. traveling upstream.  Another crucial detail is whether IP is prepared to
  626. delete the interface control structures.  In some versions of stream TCP/IP,
  627. much of the rest of the networking code is unprepared to deal with the
  628. possibility of such deletions. For example, route table entries often point
  629. to the per-interface structure; if these are not cleaned up, problems can
  630. occur.  In fact, some early implementations of SLIP for 4.2bsd were known to
  631. crash when the interface was deleted.
  632.  
  633. -0
  634.  
  635. .5
  636.  
  637. 1
  638.  
  639. 1.5
  640.  
  641. 2
  642.  
  643. Packet Size
  644.  
  645. time ratio
  646.  
  647. 0 200 400 600 800 1000 1200 1400
  648.  
  649. Figure 5. Ratio of Median Times -- Long Haul
  650.  
  651. The 9th Edition implementation of stream TCP/IP deals well enough with
  652. shutdowns; however, the IP destination address is not passed downstream
  653. along with the packet unless ARP [Plum82]
  654.  
  655. is  in  use.  The  implementation  is  thus  able  to  deal  only  with
  656. Ethernet 5 networks and point-to point links, for which the concept of
  657. destination address is not relevant.  This is obviously easy to fix.
  658.  
  659. System  V  versions  typically  use  the Data  Link  Provider  Interface
  660. (DLPI) [McGr89] protocol between IP and the device driver.  The Pnet server
  661. must implement its half of this protocol, a non-trivial matter.  DLPI does
  662. provide for the destination address to be passed along. Unfortunately, it
  663. also introduces another complication at shutdown: the protocol requires that
  664. a link be unbound at connection tear-down, via a DL_UNBIND_REQ message and
  665. acknowledgement.  This is not difficult for a resident device driver, but is
  666. problematic when the ``device'' is a pipe.  Shutdown can occur when a server
  667. program has exited; there is obviously no way for the server to receive or
  668. send any more messages.
  669.  
  670. We worked with a pre-release version of the System V Release 4 streams
  671. TCP/IP, based on the Lachman/Convergent code; for it, some of these concerns
  672. were minimized.  For example, although the drivers do acknowledge IP's
  673. DL_UNBIND_REQ message, the acknowledgement is silently ignored; thus, its
  674. absence is not missed.  Similarly, while some implementation-specific
  675. details -- for example, associating the stream with a statistics structure,
  676. and actually keeping
  677.  
  678. ________________
  679.  
  680. 5.  Ethernet is a registered trademark of Xerox Corporation.
  681.  
  682. 1
  683.  
  684. 1.2
  685.  
  686. 1.4
  687.  
  688. Packet Size
  689.  
  690. difference
  691.  
  692. 0 200 400 600 800 1000 1200 1400
  693.  
  694.  
  695. Long Haul
  696.  
  697. Figure 6. Time Differences
  698.  
  699. counts  in  that  structure  --  are  messy,  the  existing  drivers  in
  700. our version ignored them, so we ignored them as well.
  701.  
  702. Given that, we must implement the following aspects of the protocol:
  703.  
  704. * Respond  to DL_BIND_REQ with  a DL_BIND_ACK message.  Since  both  of
  705. these messages are transmitted as M_PROTO streams messages, they could be
  706. sent and received easily enough via putmsg() and getmsg().
  707.  
  708. * Respond  to  a DL_INFO_REQ message  with  a DL_INFO_ACK message.  Again,
  709. this requires no kernel code.
  710.  
  711. * Accept and send data via DL_UNITDATA_REQ and DL_UNITDATA_IND.
  712.  
  713. * Accept  a  few ioctl()  calls.  This  version  of  IP  requires  that  the
  714. socket ioctl() calls, notably SIOCSIFFLAGS, SIOCSIFADDR, and SIOCSIFNAME (to
  715. set the interface structure name) be fielded by the driver (or a convergence
  716. module), and an M_IOCACK message sent back upstream.  This one is more
  717. difficult, since there is no way to process M_IOCTL messages at the stream
  718. head, or to generate responses.
  719.  
  720. We  could  have  implemented  this  via  a  special-purpose  module. 
  721. Indeed, if a module were needed anyway, to handle DL_UNBIND_REQ, we would
  722. probably have opted for that solution. Given that everything else could be
  723. handled at user level, though, we provided a general alternative, the
  724. mesg/rmesg module pair used in 9th Edition systems.  These modules
  725. encapsulate all stream messages, regardless of type, as an M_DATA message
  726. preceeded by an M_PROTO header.  In the reverse direction, a user-generated
  727. header is examined to produce an
  728.  
  729. arbitrary-type  message  from  the  data  portion  written  via putmsg(). 6
  730. A consequence of this is that even the DLPI messages are encapsulated this
  731. way; thus, the user process is slightly more complex than might otherwise be
  732. the case.
  733.  
  734. A  few  minor  changes  were  needed  to  the  implementation  of  IP.  Most
  735. important, IP needs to recognize the M_HANGUP message, to indicate that the
  736. pipe has been closed.  The proper response to this is to delete the data
  737. structure identifying a stream, and to delete any routing table entries
  738. pointing to it.  The routing table adjustments should also be made when an
  739. I_UNLINK message is received for any stream; the lack of such could be
  740. considered a bug in IP regardless of of the presence of Pnet.
  741.  
  742. Finally,  although  the  current  code  permits  a  stream  to  be  attached
  743. via either I_LINK or I_PLINK, the latter is inappropriate for a pipe.  If
  744. the owning process dies, the user end of the pipe will be closed, thus
  745. generating an M_HANGUP and disabling the stream.  The IP end, though, will
  746. be permanently attached; no process is likely to come along and issue the
  747. appropriate I_PUNLINK.  Nor is there any significant benefit to the user
  748. process in being able to do a persistent link.  Consequently, IP should
  749. reject I_PLINK calls for pipes. Unfortunately, that is not easy to do; the
  750. check is very implementation-dependent. Consequently, we have omitted it in
  751. this prototype.
  752.  
  753. 7.  CONCLUSIONS
  754.  
  755. We  have  demonstrated  how  one  simple  piece  of  code  can  be  used  to
  756. create a variety of powerful mechanisms.  Given comparatively minor changes
  757. to the stream versions of IP, it woas simpler yet.  We have implemented some
  758. of the applications described above; work on others is in progress, notably
  759. Greyer.
  760.  
  761. REFERENCES
  762.  
  763. [BFE]  ``Blacker  Front  End  Interface  Control  Document,''  pp.  1-25-
  764. 1-40 in DDN Protocol Handbook, ed. E.J. Feinler, O.J. Jacobsen, M.K. Stahl,
  765. and C.A. Ward.
  766.  
  767. [Bell89]  S.M.  Bellovin,  ``Security  Problems  in  the  TCP/IP  Protocol
  768. Suite,'' Computer Communications Review 19(2), pp. 32-48 (April, 1989).
  769.  
  770. [Brad89]  R.T.  Braden,ed.,  ``Requirements  for  Internet  hosts  -
  771. communication layers.,'' RFC 1122 (October 1989).
  772.  
  773. [Come88]  D.  Comer, Internetworking  with  TCP/IP  :  Principles,
  774. Protocols, and Architecture, Prentice-Hall, Inc. (1988).
  775.  
  776. [Denn81]  D.E.  Denning  and  G.M.  Sacco,  ``Timestamps  in  Key
  777. Distribution Protocols,'' Communications of the ACM 24(8), pp. 533-536, ACM
  778. (August 1981).
  779.  
  780. ________________
  781.  
  782. 6.  In practice, life is a bit more complex; M_FLUSH messages must be
  783. processed both in the kernel and sent to the user process.  Furthermore,
  784. security considerations dictate that use of mesg/rmesg be restricted to the
  785. superuser.
  786.  
  787. [Estr89]  D.  Estrin,  J.C.  Mogul,  and  G.  Tsudik,  ``Visa  Protocols
  788. for Controlling Inter Organization Datagram Flow,'' IEEE Journal on Selected
  789. Areas in Communications 7(4), pp. 486-498, (Special Issue on Secure
  790. Communications) (May 1989).
  791.  
  792. [Fein85]  E.J.  Feinler,  O.J. Jacobsen,  M.K.  Stahl,  and  C.A.  Ward, DDN
  793. Protocol Handbook, DDN Network Information Center, SRI International (1985).
  794.  
  795. [Jaco88]  V. Jacobson, ``Congestion Avoidance and Control,'' pp. 314-329 in
  796. Proceedings of SIGCOMM '88 (August 1988).
  797.  
  798. [Karn87]  P.  Karn  and  C.  Partridge,  ``Improving  Round-Trip  Estimates
  799. in Reliable Transport Protocols,'' pp. 2-7 in Proceedings of SIGCOMM '87
  800. (August 1987).
  801.  
  802. [Lanz89]  L.  Lanzillo  and  C.  Partridge,  ``Implementation  of  Dial-Up
  803. IP for UNIX Systems,'' in Proc. Winter USENIX Conference, San Diego,
  804. California (January, 1989).
  805.  
  806. [McGr89]  G.J.  McGrath,  ``DPLI  Interface  Specifications.,''  AT&T  White
  807. Paper (February 1989).
  808.  
  809. [Mogu89]  J.  Mogul,  ``Simple  and  Flexible  Datagram  Access  Controls
  810. for UNIX-based Gateways,'' in Proc.  Summer USENIX Conference, Baltimore,
  811. Maryland (June, 1989).
  812.  
  813. [Morr85]  R.T.  Morris,  ``A  Weakness  in  the  4.2BSD  UNIX TCP/IP
  814. Software,'' Computing Science Technical Report No.  117, AT&T Bell
  815. Laboratories, Murray Hill, New Jersey (February 1985).
  816.  
  817. [Mund87]  G.R.  Mundy  and  R.W.  Shirey,  ``Defense  Data  Network
  818. Security Architecture,'' in Proc. MILCOM '87, IEEE, Washington, D.C. (1987).
  819.  
  820. [Need78]  R.M.  Needham  and  M.  Schroeder,  ``Using  Encryption  for
  821. Authentication in Large Networks of Computers,'' Communications of the ACM
  822. 21(12), pp. 993-999, ACM (December, 1978).
  823.  
  824. [Need87]  R.M.  Needham  and  M.  Schroeder,  ``Authentication  Revisited,''
  825. Operating Systems Review 21(1), p. 7 (January 1987).
  826.  
  827. [Nowi89]  B.  Nowicki,  ``Transport  Issues  in  the  Network  File
  828. System,'' Computer Communications Review 19(2), pp. 16-20 (April, 1989).
  829.  
  830. [Plum82]  D.C.  Plummer,  ``Ethernet  Address  Resolution  Protocol:  Or
  831. converting network protocol addresses to 48.bit Ethernet address for
  832. transmission on Ethernet hardware.,'' RFC 826 (November 1982).
  833.  
  834. [Ritc84]  D.M.  Ritchie,  ``A  Stream  Input-Output  System,'' AT&T  Bell
  835. Laboratories Technical Journal 63(8, part 2), pp. 1897-1910 (October 1984).
  836.  
  837. [Romk88]  J.L.  Romkey,  ``Nonstandard  for  transmission  of  IP  datagrams
  838. over serial lines: SLIP.,'' RFC 1055 (June 1988).
  839.  
  840. [SP3]  SDNS  Protocol  and  Signalling  Working  Group,  SP3  Sub-Group,
  841. ``SDNS Secure Data Networking System Security Protocol 3 (SP3),'' SDN.301
  842. (July 12, 1988).
  843.  
  844. [Stei88]  J.  Steiner,  C.  Neuman,  and  J.I.  Schiller,  ``Kerberos:  An
  845. Authentication Service for Open Network Systems,'' in Proc. Winter USENIX
  846. Conference, Dallas (1988).
  847.  
  848.